import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution56 {
    public int[][] merge(int[][] intervals) {
        int length = intervals.length;
        Arrays.sort(intervals, (int[] interval1, int[] interval2) -> {
            int leftNum = interval1[0], rightNum = interval2[0];
            if(leftNum == rightNum){ return 0; }
            else if(leftNum < rightNum){ return -1; }
            else{ return 1; }
        });
        List<int[]> resList = new ArrayList<>();
        for(int i = 0; i < length; i++){
            int intervalLeft = intervals[i][0], intervalRight = intervals[i][1];
            while(i + 1 < length && intervalRight >= intervals[i + 1][0]){
                intervalRight = Math.max(intervalRight, intervals[++i][1]);
            }
            resList.add(new int[]{intervalLeft, intervalRight});
        }
        return resList.toArray(new int[resList.size()][]);
    }

    public static void main(String[] args) {
        Solution56 s = new Solution56();
        s.merge(new int[][]{{1,3},{2,6},{8,10},{15,18}});
    }
}
